#include<iostream>
#include<fstream>
#include<algorithm>
using namespace std;

class Solution
{
public:
    //返回 i到最后 最大的价值 0 - 1en-1
    int process(int weights[],int values[],int len,int i,int alreadyweight,int bag) {
        if(i >= len || alreadyweight >= bag) {
            return 0;
        }
        if(weights[i] + alreadyweight > bag) {
            //无法装入i物品
            return process(weights,values,len,i+1,alreadyweight,bag);
        } else {
            //装入 或 不装入
            return max(process(weights,values,len,i+1,alreadyweight+weights[i],bag)+values[i],
                process(weights,values,len,i+1,alreadyweight,bag));
        }
    }
};
int weights[20],values[20]; //物品重量 价值
int bags,len; //最大承重 物品数目

ifstream in("in.txt");

int main() {
    in >> len >> bags;
    for(int i=0; i<len; i++) {
        in >> weights[i] >> values[i];
    }
    int res = Solution().process(weights,values,len,0,0,bags);
    cout << "max value:" << res << endl;
    return 0;
}